{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#!/usr/bin/env python\n",
    "# coding: utf-8\n",
    "\n",
    "# In[1]:\n",
    "\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "# In[ ]:\n",
    "\n",
    "\n",
    "class D_TREE :\n",
    "    \n",
    "    def fit(self,Xin):\n",
    "        #fitting the values\n",
    "        self.X=Xin                            #training_dataset_\n",
    "        self.my_tree=self.tree(Xin)           #calls tree() function to create a tree based on the dataset provided\n",
    "    \n",
    "    \n",
    "    \n",
    "    def label_count(self,t):\n",
    "        #count the unique labels\n",
    "        count = {}                           #a dictionary that will store the no of times every label has occurred\n",
    "        for i in range(len(t)):\n",
    "            lbl = t[i][-1]                   #The last field or column in t actually contains the labels \n",
    "            if lbl not in count:\n",
    "                count[lbl] = 0               #If the label is not present previously,initialize it with zero\n",
    "            count[lbl]+=1                    #Everytime a particular label is encountered its count is increased by 1           \n",
    "        return count\n",
    "\n",
    "    \n",
    "    \n",
    "    \n",
    "    class Question :\n",
    "        #stores the question and matches the question \n",
    "        def __init__(self,col,value):\n",
    "            self.col = col                  #The column to which the question belongs to\n",
    "            self.question = value           #the particualr cell in the column which is treated as question\n",
    "        \n",
    "        \n",
    "        def is_digit_or_char(self,n):\n",
    "            #checks whether a particular value is a number or not\n",
    "            return isinstance(n,int) or isinstance(n,float)\n",
    "    \n",
    "        def check(self,row):\n",
    "            value=row[self.col]              #the value to be tested with the question\n",
    "            if(self.is_digit_or_char(self.question)):\n",
    "                return value>=self.question  #if the value is numeric in nature check whether it is greater or equal to question\n",
    "            else :\n",
    "                return value==self.question  #if the value is a character or string check whether it is equal to the question or not\n",
    "         \n",
    "        \n",
    "   \n",
    "\n",
    "    def gini(self,t):\n",
    "        #Calculates the gini score\n",
    "        label = np.unique(t)                #No of unique labels\n",
    "        impurity = 1\n",
    "    \n",
    "        for i in range(len(label)):\n",
    "            impurity -= (np.sum(t[:,-1]==label[i])/t.shape[0])**2    #formula for calculating impurity based on probability\n",
    "    \n",
    "        return impurity\n",
    "\n",
    "    \n",
    "    \n",
    "\n",
    "    def information_gain(self,l,r,current_uncertainity):\n",
    "        #Information gain is calculated\n",
    "        p = len (l) / float ( len(l) + len(r) )             \n",
    "        return current_uncertainity - p*self.gini(l) - (1-p)*self.gini(r)\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    def best_split(self,t):\n",
    "        #Selects the best question and split based on the gini score\n",
    "        maxm=0\n",
    "        best_question = None\n",
    "        tr_row=[]\n",
    "        fl_row=[]\n",
    "            \n",
    "        for i in range(t.shape[1]-1):\n",
    "            y=np.unique(t[:,i])                         #no of unique labels in a particular column\n",
    "            m=y.shape[0]                                #no of examples\n",
    "            for j in range(m):\n",
    "                question = self.Question(i,y[j])        #each unique label is considered a question one at a time\n",
    "                tr_row , fl_row = self.split(t,question)#splits the rows based on the question\n",
    "                if(len(fl_row)==0 or len(tr_row)==0):\n",
    "                    continue                            #if any of the branch has zero rows,the question is skipped\n",
    "                \n",
    "                info_gain= self.information_gain(tr_row,fl_row,self.gini(t))  #information gain is calculated\n",
    "                \n",
    "                if(info_gain>maxm):\n",
    "                    \"\"\"best question\n",
    "                       with maximum informaion\n",
    "                       gain is selected\"\"\"\n",
    "                    maxm = info_gain                 \n",
    "                    best_question = question\n",
    "                \n",
    "        return maxm,best_question\n",
    "\n",
    "    \n",
    "    \n",
    "   \n",
    "    def split(self,t,question)\n",
    "    #Splits the dataset based on the best question\n",
    "        tr_row=[]       \n",
    "        fl_row=[]\n",
    "        for k in range(t.shape[0]):\n",
    "            \"\"\"checks every row of the dataset \n",
    "               with the queston & if it matches,\n",
    "               it is appended to the true rows\n",
    "               else to the false rows\"\"\"\n",
    "            if question.check(t[k]):\n",
    "                tr_row=np.append(tr_row,t[k])   \n",
    "            else:\n",
    "                fl_row=np.append(fl_row,t[k])\n",
    "                    \n",
    "        tr_row = np.reshape(tr_row,(len(tr_row)//t.shape[1],t.shape[1]))   #just reshapes the one-d matrix into a readable 2d matrix\n",
    "        fl_row = np.reshape(fl_row,(len(fl_row)//t.shape[1],t.shape[1]))   #just reshapes the one-d matrix into a readable 2d matrix\n",
    "    \n",
    "        return tr_row,fl_row\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    class Decision_Node:\n",
    "        #Stores the different question,true branch and false branch for all parts of the tree\n",
    "        def __init__(self,question,true_branch,false_branch):\n",
    "            self.question = question                        \n",
    "            self.true_branch = true_branch\n",
    "            self.false_branch = false_branch\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "    class Leaf:\n",
    "        #the terminal of a tree is the leaf\n",
    "        def __init__(self,t):\n",
    "            self.predictions = D_TREE().label_count(t)    \n",
    "\n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "    def tree(self,t):\n",
    "        \"\"\"the most important part of the entire algorithm\n",
    "        this is where the tree is constructed from the root \n",
    "        to the leaves\"\"\"\n",
    "        gain,question = self.best_split(t)                #best question with maximum gain is selected\n",
    "        if(gain==0):\n",
    "            return self.Leaf(t)                           #no gain indicates that leaf is reached\n",
    "        \n",
    "        \"\"\"if the control has reached this far,it means\n",
    "        there is useful gain and teh datset can be subdivided\n",
    "        or branched into true rows and false rows\"\"\"\n",
    "        true_rows , false_rows = self.split(t,question)    \n",
    "        true_node = self.tree(true_rows)                  #A recursion is carried out till all the true rows are found out\n",
    "        false_node= self.tree(false_rows)                 #after true rows,the false rows are assigned to the node in a reverse fashion\n",
    "                                                            \n",
    "        return self.Decision_Node(question,true_node,false_node)  \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    def check_testing_data(self,test,node):\n",
    "        #checks the testing data by recursively calling itself\n",
    "        if isinstance(node,self.Leaf):\n",
    "            return node.predictions        #when the leaf is reached prediction is made\n",
    "        \n",
    "        \"\"\"a row is made to travel in the tree,till it reaches a leaf,\n",
    "           it is checked with all decision nodes, and accordingly\n",
    "           it travels along true branch or false branch,till\n",
    "           it reaches a leaf\"\"\"\n",
    "        if(node.question.check(test)):\n",
    "            return self.check_testing_data(test,node.true_branch)\n",
    "        else:\n",
    "            return self.check_testing_data(test,node.false_branch)\n",
    "        \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    def print_leaf(self,LEAF):\n",
    "        #prints a leaf\n",
    "        p={}\n",
    "        for i in LEAF.keys():\n",
    "            p[i] = str(100*LEAF[i]/float(sum(LEAF.values()))) + \"%\"\n",
    "        \n",
    "        print(p)\n",
    "        \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    def pred(self,X_test):\n",
    "        #predicts values for test data\n",
    "        y_pred=[0]*X_test.shape[0]\n",
    "        for i in range(X_test.shape[0]):\n",
    "            \"\"\"when a row reaches a particular leaf\n",
    "               it is assigned the label which\n",
    "               appears maximum in the leaf\"\"\"\n",
    "            r= self.check_testing_data(X_test[i],self.my_tree)      #deals with one row at a time\n",
    "            y_pred[i] = max(r.keys(), key=(lambda k: r[k]))         \n",
    "        return y_pred\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    def accuracy(self,y_test,y_pred):\n",
    "        #Calculate the accuracy of the model\n",
    "        return np.mean(y_test==y_pred)*100\n",
    "    \n",
    "    \n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Importing libraries\n",
    "import numpy as np\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Importing data set\n",
    "from sklearn.datasets import load_breast_cancer\n",
    "data = load_breast_cancer()\n",
    "\n",
    "\n",
    "X=data['data']\n",
    "Y=data['target']\n",
    "Y=np.reshape(Y,(Y.shape[0],1))\n",
    "X=X[:,:5]\n",
    "X=np.append(X,Y,axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Separating training set and test set\n",
    "sz = len(X)//4\n",
    "X_test=X[:sz,:]\n",
    "X_train=X[sz:,:]   #X_train already contains Y_train as its last column so no need to define it separately\n",
    "Y_test=X_test[:,-1]\n",
    "n=X.shape[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Training the algorithm\n",
    "train=D_TREE()\n",
    "train.fit(X_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Predictions on test data\n",
    "y_pred=train.pred(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1.0: '100.0%'}\n",
      "{0.0: '100.0%'}\n",
      "{0.0: '100.0%'}\n",
      "{1.0: '100.0%'}\n",
      "{0.0: '100.0%'}\n",
      "{1.0: '100.0%'}\n",
      "{0.0: '100.0%'}\n",
      "{0.0: '100.0%'}\n",
      "{0.0: '100.0%'}\n",
      "{1.0: '100.0%'}\n"
     ]
    }
   ],
   "source": [
    "#A few predictions\n",
    "for i in range(10):\n",
    "    train.print_leaf(train.check_testing_data(X_test[i],train.my_tree))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy of my model :  80.28169014084507 %\n"
     ]
    }
   ],
   "source": [
    "print(\"Accuracy of my model : \",train.accuracy(Y_test,y_pred),\"%\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "accuracy of sklearn model =  80.28169014084507 %\n"
     ]
    }
   ],
   "source": [
    "#calculating accuracy using sklearn model\n",
    "from sklearn import tree\n",
    "clf = tree.DecisionTreeClassifier()\n",
    "clf = clf.fit(X_train[:,0:n-1], Y_train)\n",
    "y_pred=clf.predict(X_test[:,:n-1])\n",
    "error=(y_pred==Y_test.flatten())\n",
    "print(\"accuracy of sklearn model = \",np.mean(error)*100,\"%\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
